home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / Pascal / Snippets / PNL Libraries / Libraries / RegExp / regexp.c next >
Text File  |  1996-12-17  |  32KB  |  1,354 lines
  1. /* 
  2.  *
  3.  * regexp.c - regular expression matching
  4.  *
  5.  * DESCRIPTION
  6.  *
  7.  *        Underneath the reformatting and comment blocks which were added to 
  8.  *        make it consistent with the rest of the code, you will find a
  9.  *        modified version of Henry Specer's regular expression library.
  10.  *        Henry's functions were modified to provide the minimal regular
  11.  *        expression matching, as required by P1003.  Henry's code was
  12.  *        copyrighted, and copy of the copyright message and restrictions
  13.  *        are provided, verbatim, below:
  14.  *
  15.  *        Copyright (c) 1986 by University of Toronto.
  16.  *        Written by Henry Spencer.  Not derived from licensed software.
  17.  *
  18.  *        Permission is granted to anyone to use this software for any
  19.  *        purpose on any computer system, and to redistribute it freely,
  20.  *        subject to the following restrictions:
  21.  *
  22.  *        1. The author is not responsible for the consequences of use of
  23.  *         this software, no matter how awful, even if they arise
  24.  *           from defects in it.
  25.  *
  26.  *        2. The origin of this software must not be misrepresented, either
  27.  *           by explicit claim or by omission.
  28.  *
  29.  *        3. Altered versions must be plainly marked as such, and must not
  30.  *           be misrepresented as being the original software.
  31.  *
  32.  *
  33.  * This version modified by Ian Phillipps to return pointer to terminating
  34.  * NUL on substitution string. [ Temp mail address ex-igp@camcon.co.uk ]
  35.  *
  36.  *        Altered by amylaar to support excompatible option and the
  37.  *      operators \< and >\ . ( 7.Sep. 1991 )
  38.  *
  39.  * regsub altered by amylaar to take an additional parameter specifying
  40.  * maximum number of bytes that can be written to the memory region
  41.  * pointed to by dest
  42.  *
  43.  *         Beware that some of this code is subtly aware of the way operator
  44.  *         precedence is structured in regular expressions.  Serious changes in
  45.  *         regular-expression syntax might require a total rethink.
  46.  *
  47.  * AUTHORS
  48.  *
  49.  *     Mark H. Colburn, NAPS International (mark@jhereg.mn.org)
  50.  *     Henry Spencer, University of Torronto (henry@utzoo.edu)
  51.  *
  52.  * Sponsored by The USENIX Association for public distribution. 
  53.  *
  54.  */
  55.  
  56. /* Headers */
  57.  
  58. #include <stdio.h>
  59. #include <stdlib.h>
  60. #include <string.h>
  61. #include <ctype.h>
  62. #include "regexp.h"
  63. /* #include "config.h" */
  64. /* #include "lint.h" /* for FREE() */
  65.  
  66. #define MYFREE free
  67. #define MYALLOC malloc
  68. #define DXALLOC( N, CODE, NAME ) MYALLOC(N)
  69.  
  70. /*
  71.  * The "internal use only" fields in regexp.h are present to pass info from
  72.  * compile to execute that permits the execute phase to run lots faster on
  73.  * simple cases.  They are:
  74.  *
  75.  * regstart        char that must begin a match; '\0' if none obvious
  76.  * reganch        is the match anchored (at beginning-of-line only)?
  77.  * regmust        string (pointer into program) that match must include, or NULL
  78.  * regmlen        length of regmust string
  79.  *
  80.  * Regstart and reganch permit very fast decisions on suitable starting points
  81.  * for a match, cutting down the work a lot.  Regmust permits fast rejection
  82.  * of lines that cannot possibly match.  The regmust tests are costly enough
  83.  * that regcomp() supplies a regmust only if the r.e. contains something
  84.  * potentially expensive (at present, the only such thing detected is * or +
  85.  * at the start of the r.e., which can involve a lot of backup).  Regmlen is
  86.  * supplied because the test in regexec() needs it and regcomp() is computing
  87.  * it anyway.
  88.  */
  89.  
  90. /*
  91.  * Structure for regexp "program".  This is essentially a linear encoding
  92.  * of a nondeterministic finite-state machine (aka syntax charts or
  93.  * "railroad normal form" in parsing technology).  Each node is an opcode
  94.  * plus a "nxt" pointer, possibly plus an operand.  "Nxt" pointers of
  95.  * all nodes except BRANCH implement concatenation; a "nxt" pointer with
  96.  * a BRANCH on both ends of it is connecting two alternatives.  (Here we
  97.  * have one of the subtle syntax dependencies:  an individual BRANCH (as
  98.  * opposed to a collection of them) is never concatenated with anything
  99.  * because of operator precedence.)  The operand of some types of node is
  100.  * a literal string; for others, it is a node leading into a sub-FSM.  In
  101.  * particular, the operand of a BRANCH node is the first node of the branch.
  102.  * (NB this is *not* a tree structure:  the tail of the branch connects
  103.  * to the thing following the set of BRANCHes.)  The opcodes are:
  104.  */
  105.  
  106. /* definition        number        opnd?        meaning */
  107. #define        END        0                /* no        End of program. */
  108. #define        BOL        1                /* no        Match "" at beginning of line. */
  109. #define        EOL        2                /* no        Match "" at end of line. */
  110. #define        ANY        3                /* no        Match any one character. */
  111. #define        ANYOF        4                /* str        Match any character in this string. */
  112. #define        ANYBUT        5                /* str        Match any character not in this
  113.                                  * string. */
  114. #define        BRANCH        6                /* node        Match this alternative, or the
  115.                                  * nxt... */
  116. #define        BACK        7                /* no        Match "", "nxt" ptr points backward. */
  117. #define        EXACTLY        8                /* str        Match this string. */
  118. #define        NOTHING        9                /* no        Match empty string. */
  119. #define        STAR        10                /* node        Match this (simple) thing 0 or more
  120.                                  * times. */
  121. #define WORDSTART 11                /* node matching a start of a word          */
  122. #define WORDEND 12                /* node matching an end of a word           */
  123. #define        OPEN        20                /* no        Mark this point in input as start of
  124.                                  * #n. */
  125.  /* OPEN+1 is number 1, etc. */
  126. #define        CLOSE        30                /* no        Analogous to OPEN. */
  127.  
  128. /*
  129.  * Opcode notes:
  130.  *
  131.  * BRANCH        The set of branches constituting a single choice are hooked
  132.  *                together with their "nxt" pointers, since precedence prevents
  133.  *                anything being concatenated to any individual branch.  The
  134.  *                "nxt" pointer of the last BRANCH in a choice points to the
  135.  *                thing following the whole choice.  This is also where the
  136.  *                final "nxt" pointer of each individual branch points; each
  137.  *                branch starts with the operand node of a BRANCH node.
  138.  *
  139.  * BACK                Normal "nxt" pointers all implicitly point forward; BACK
  140.  *                exists to make loop structures possible.
  141.  *
  142.  * STAR                complex '*', are implemented as circular BRANCH structures 
  143.  *                using BACK.  Simple cases (one character per match) are 
  144.  *                implemented with STAR for speed and to minimize recursive 
  145.  *                plunges.
  146.  *
  147.  * OPEN,CLOSE        ...are numbered at compile time.
  148.  */
  149.  
  150. /*
  151.  * A node is one char of opcode followed by two chars of "nxt" pointer.
  152.  * "Nxt" pointers are stored as two 8-bit pieces, high order first.  The
  153.  * value is a positive offset from the opcode of the node containing it.
  154.  * An operand, if any, simply follows the node.  (Note that much of the
  155.  * code generation knows about this implicit relationship.)
  156.  *
  157.  * Using two bytes for the "nxt" pointer is vast overkill for most things,
  158.  * but allows patterns to get big without disasters.
  159.  */
  160. #define        OP(p)        (*(p))
  161. #define        NEXT(p)        (((*((p)+1)&0377)<<8) + (*((p)+2)&0377))
  162. #define        OPERAND(p)        ((p) + 3)
  163.  
  164. /*
  165.  * Utility definitions.
  166.  */
  167.  
  168. #define SPECIAL 0x100
  169. #define LBRAC        ('('|SPECIAL)
  170. #define RBRAC        (')'|SPECIAL)
  171. #define ASTERIX        ('*'|SPECIAL)
  172. #define OR_OP        ('|'|SPECIAL)
  173. #define DOLLAR        ('$'|SPECIAL)
  174. #define DOT        ('.'|SPECIAL)
  175. #define CARET        ('^'|SPECIAL)
  176. #define LSQBRAC ('['|SPECIAL)
  177. #define RSQBRAC (']'|SPECIAL)
  178. #define LSHBRAC ('<'|SPECIAL)
  179. #define RSHBRAC ('>'|SPECIAL)
  180. #define        FAIL(m)        { regerror(m); return(NULL); }
  181. #define        ISMULT(c)        ((c) == ASTERIX)
  182. #define        META        "^$.[()|*\\"
  183. #ifndef CHARBITS
  184. #define CHARBITS        0xff
  185. #define        UCHARAT(p)        ((long)*(unsigned char *)(p))
  186. #else
  187. #define        UCHARAT(p)        ((long)*(p)&CHARBITS)
  188. #endif
  189. #define ISWORDPART(c) ( isalnum(c) || (c) == '_' )
  190.  
  191. /*
  192.  * Flags to be passed up and down.
  193.  */
  194. #define        HASWIDTH        01        /* Known never to match null string. */
  195. #define        SIMPLE                02        /* Simple enough to be STAR operand. */
  196. #define        SPSTART                04        /* Starts with * */
  197. #define        WORST                0        /* Worst case. */
  198.  
  199. /*
  200.  * Global work variables for regcomp().
  201.  */
  202. static short   *regparse;        /* Input-scan pointer. */
  203. static long      regnpar;        /* () count. */
  204. static char     regdummy;
  205. static char    *regcode;        /* Code-emit pointer; ®dummy = don't. */
  206. static long     regsize;        /* Code size. */
  207.  
  208. /*
  209.  * Forward declarations for regcomp()'s friends.
  210.  */
  211. static char    *reg();
  212. static char    *regbranch();
  213. static char    *regpiece();
  214. static char    *regatom();
  215. static char    *regnode();
  216. static char    *regnext();
  217. static void     regc();
  218. static void     reginsert();
  219. static void     regtail();
  220. static void     regoptail();
  221.  
  222. static long strncasedifferent( char *s, char *t, long len )
  223. {
  224.     while ( len > 0 ) {
  225.         if ( toupper(*s) != toupper(*t) ) {
  226.             return 1;
  227.         }
  228.         s++;
  229.         t++;
  230.         len--;
  231.     }
  232.     return 0;
  233. }
  234.  
  235. static char *strcasechr( char *s, char ch )
  236. {
  237.     ch = toupper(ch);
  238.     while ( *s && toupper(*s) != ch ) {
  239.         s++;
  240.     }
  241.     if ( *s ) {
  242.         return s;
  243.     } else {
  244.         return NULL;
  245.     }
  246. }
  247. pascal void regfree(regexp *prog)
  248. {
  249.     MYFREE((char*)prog);
  250. }
  251.  
  252. /*
  253.  - regcomp - compile a regular expression into internal code
  254.  *
  255.  * We can't allocate space until we know how big the compiled form will be,
  256.  * but we can't compile it (and thus know how big it is) until we've got a
  257.  * place to put the code.  So we cheat:  we compile it twice, once with code
  258.  * generation turned off and size counting turned on, and once "for real".
  259.  * This also means that we don't allocate space until we are sure that the
  260.  * thing really will compile successfully, and we never have to move the
  261.  * code and thus invalidate pointers into it.  (Note that it has to be in
  262.  * one piece because FREE() must be able to free it all. - NOT - PNL)
  263.  *
  264.  * Beware that the optimization-preparation code in here knows about some
  265.  * of the structure of the compiled regexp.
  266.  */
  267. pascal regexp *regcomp(char *exp, long excompat)
  268.         /* excompat - \( \) operators like in unix ex */
  269. {
  270.     register regexp *r;
  271.     register char  *scan;
  272.     register char  *longest;
  273.     register long    len;
  274.     long             flags;
  275.     short           *exp2,*dest,c;
  276.     extern char    *xalloc();
  277.  
  278.     if (exp == (char *)NULL)
  279.         FAIL("NULL argument");
  280.  
  281.     exp2=(short*)
  282.         DXALLOC( (strlen(exp)+1) * (sizeof(short[8])/sizeof(char[8])), 94,
  283.                 "regcomp: 1" );
  284.     scan=exp;
  285.     dest=exp2;
  286.     while ( (c= *scan++) != 0 ) {
  287.         switch (c) {
  288.             case '(':
  289.             case ')':
  290.                 *dest++ = excompat ? c : c | SPECIAL;
  291.                 break;
  292.             case '.':
  293.             case '*':
  294.             case '|':
  295.             case '$':
  296.             case '^':
  297.             case '[':
  298.             case ']':
  299.                 *dest++ =  c | SPECIAL;
  300.                 break;
  301.             case '\\':
  302.                 switch ( c = *scan++ ) {
  303.                     case '(':
  304.                     case ')':
  305.                         *dest++ = excompat ? c | SPECIAL : c;
  306.                         break;
  307.                     case '<':
  308.                     case '>':
  309.                         *dest++ = c | SPECIAL;
  310.                         break;
  311.                     case '{':
  312.                     case '}':
  313.                         FAIL("sorry, unimplemented operator");
  314.                     case 'b': *dest++ = '\b'; break;
  315.                     case 't': *dest++ = '\t'; break;
  316.                     case 'r': *dest++ = '\r'; break;
  317.                     default:
  318.                         *dest++ = c;
  319.                 }
  320.                 break;
  321.             default:
  322.                 *dest++ = c;
  323.         }
  324.     }
  325.     *dest=0;
  326.     /* First pass: determine size, legality. */
  327.     regparse = exp2;
  328.     regnpar = 1;
  329.     regsize = 0L;
  330.     regcode = ®dummy;
  331.     regc(MAGIC);
  332.     if (reg(0, &flags) == (char *)NULL)
  333.         return ((regexp *)NULL);
  334.  
  335.     /* Small enough for pointer-storage convention? */
  336.     if (regsize >= 32767L)        /* Probably could be 65535L. */
  337.         FAIL("regexp too big");
  338.  
  339.     /* Allocate space. */
  340.     r = (regexp *) DXALLOC(sizeof(regexp) + (unsigned) regsize, 95,
  341.                 "regcomp: 2");
  342.     if (r == (regexp *) NULL)
  343.         FAIL("out of space");
  344.  
  345.     /* Second pass: emit code. */
  346.     regparse = exp2;
  347.     regnpar = 1;
  348.     regcode = r->program;
  349.     regc(MAGIC);
  350.     if (reg(0, &flags) == NULL)
  351.         return ((regexp *) NULL);
  352.  
  353.     /* Dig out information for optimizations. */
  354.     r->regstart = '\0';                /* Worst-case defaults. */
  355.     r->reganch = 0;
  356.     r->regmust = NULL;
  357.     r->regmlen = 0;
  358.     scan = r->program + 1;        /* First BRANCH. */
  359.     if (OP(regnext(scan)) == END) {        /* Only one top-level choice. */
  360.         scan = OPERAND(scan);
  361.  
  362.         /* Starting-point info. */
  363.         if (OP(scan) == EXACTLY)
  364.             r->regstart = *OPERAND(scan);
  365.         else if (OP(scan) == BOL)
  366.             r->reganch++;
  367.  
  368.         /*
  369.          * If there's something expensive in the r.e., find the longest
  370.          * literal string that must appear and make it the regmust.  Resolve
  371.          * ties in favor of later strings, since the regstart check works
  372.          * with the beginning of the r.e. and avoiding duplication
  373.          * strengthens checking.  Not a strong reason, but sufficient in the
  374.          * absence of others. 
  375.          */
  376.         if (flags & SPSTART) {
  377.             longest = NULL;
  378.             len = 0;
  379.             for (; scan != NULL; scan = regnext(scan))
  380.                 if (OP(scan) == EXACTLY && strlen(OPERAND(scan)) >= len) {
  381.                     longest = OPERAND(scan);
  382.                     len = strlen(OPERAND(scan));
  383.                 }
  384.             r->regmust = longest;
  385.             r->regmlen = len;
  386.         }
  387.     }
  388.     MYFREE((char*)exp2);
  389.     return (r);
  390. }
  391.  
  392. /*
  393.  - reg - regular expression, i.e. main body or parenthesized thing
  394.  *
  395.  * Caller must absorb opening parenthesis.
  396.  *
  397.  * Combining parenthesis handling with the base level of regular expression
  398.  * is a trifle forced, but the need to tie the tails of the branches to what
  399.  * follows makes it hard to avoid.
  400.  */
  401. static char *reg(paren, flagp)
  402. long             paren;                /* Parenthesized? */
  403. long            *flagp;
  404. {
  405.     register char  *ret;
  406.     register char  *br;
  407.     register char  *ender;
  408.     register long    parno = 0;
  409.     long             flags;
  410.  
  411.     *flagp = HASWIDTH;                /* Tentatively. */
  412.  
  413.     /* Make an OPEN node, if parenthesized. */
  414.     if (paren) {
  415.         if (regnpar >= NSUBEXP)
  416.             FAIL("too many ()");
  417.         parno = regnpar;
  418.         regnpar++;
  419.         ret = regnode(OPEN + parno);
  420.     } else
  421.         ret = (char *)NULL;
  422.  
  423.     /* Pick up the branches, linking them together. */
  424.     br = regbranch(&flags);
  425.     if (br == (char *)NULL)
  426.         return ((char *)NULL);
  427.     if (ret != (char *)NULL)
  428.         regtail(ret, br);        /* OPEN -> first. */
  429.     else
  430.         ret = br;
  431.     if (!(flags & HASWIDTH))
  432.         *flagp &= ~HASWIDTH;
  433.     *flagp |= flags & SPSTART;
  434.     while (*regparse == OR_OP) {
  435.         regparse++;
  436.         br = regbranch(&flags);
  437.         if (br == (char *)NULL)
  438.             return ((char *)NULL);
  439.         regtail(ret, br);        /* BRANCH -> BRANCH. */
  440.         if (!(flags & HASWIDTH))
  441.             *flagp &= ~HASWIDTH;
  442.         *flagp |= flags & SPSTART;
  443.     }
  444.  
  445.     /* Make a closing node, and hook it on the end. */
  446.     ender = regnode((paren) ? CLOSE + parno : END);
  447.     regtail(ret, ender);
  448.  
  449.     /* Hook the tails of the branches to the closing node. */
  450.     for (br = ret; br != (char *)NULL; br = regnext(br))
  451.         regoptail(br, ender);
  452.  
  453.     /* Check for proper termination. */
  454.     if (paren && *regparse++ != RBRAC) {
  455.         FAIL("unmatched ()");
  456.     } else if (!paren && *regparse != '\0') {
  457.         if (*regparse == RBRAC) {
  458.             FAIL("unmatched ()");
  459.         } else
  460.             FAIL("junk on end");/* "Can't happen". */
  461.         /* NOTREACHED */
  462.     }
  463.     return (ret);
  464. }
  465.  
  466. /*
  467.  - regbranch - one alternative of an | operator
  468.  *
  469.  * Implements the concatenation operator.
  470.  */
  471. static char  *regbranch(flagp)
  472. long            *flagp;
  473. {
  474.     register char  *ret;
  475.     register char  *chain;
  476.     register char  *latest;
  477.     long             flags;
  478.  
  479.     *flagp = WORST;                /* Tentatively. */
  480.  
  481.     ret = regnode(BRANCH);
  482.     chain = (char *)NULL;
  483.     while (*regparse != '\0' && *regparse != OR_OP && *regparse != RBRAC) {
  484.         latest = regpiece(&flags);
  485.         if (latest == (char *)NULL)
  486.             return ((char *)NULL);
  487.         *flagp |= flags & HASWIDTH;
  488.         if (chain == (char *)NULL)        /* First piece. */
  489.             *flagp |= flags & SPSTART;
  490.         else
  491.             regtail(chain, latest);
  492.         chain = latest;
  493.     }
  494.     if (chain == (char *)NULL)                /* Loop ran zero times. */
  495.         regnode(NOTHING);
  496.  
  497.     return (ret);
  498. }
  499.  
  500. /*
  501.  - regpiece - something followed by possible [*]
  502.  *
  503.  * Note that the branching code sequence used for * is somewhat optimized:  
  504.  * they use the same NOTHING node as both the endmarker for their branch 
  505.  * list and the body of the last branch.  It might seem that this node could 
  506.  * be dispensed with entirely, but the endmarker role is not redundant.
  507.  */
  508. static char *regpiece(flagp)
  509. long            *flagp;
  510. {
  511.     register char  *ret;
  512.     register short  op;
  513.     /* register char  *nxt; */
  514.     long             flags;
  515.  
  516.     ret = regatom(&flags);
  517.     if (ret == (char *)NULL)
  518.         return ((char *)NULL);
  519.  
  520.     op = *regparse;
  521.     if (!ISMULT(op)) {
  522.         *flagp = flags;
  523.         return (ret);
  524.     }
  525.     if (!(flags & HASWIDTH))
  526.         FAIL("* operand could be empty");
  527.     *flagp = (WORST | SPSTART);
  528.  
  529.     if (op == ASTERIX && (flags & SIMPLE))
  530.         reginsert(STAR, ret);
  531.     else if (op == ASTERIX) {
  532.         /* Emit x* as (x&|), where & means "self". */
  533.         reginsert(BRANCH, ret);        /* Either x */
  534.         regoptail(ret, regnode(BACK));        /* and loop */
  535.         regoptail(ret, ret);        /* back */
  536.         regtail(ret, regnode(BRANCH));        /* or */
  537.         regtail(ret, regnode(NOTHING));        /* null. */
  538.     } 
  539.     regparse++;
  540.     if (ISMULT(*regparse))
  541.         FAIL("nested *");
  542.  
  543.     return (ret);
  544. }
  545.  
  546. /*
  547.  - regatom - the lowest level
  548.  *
  549.  * Optimization:  gobbles an entire sequence of ordinary characters so that
  550.  * it can turn them into a single node, which is smaller to store and
  551.  * faster to run.
  552.  */
  553. static char *regatom(flagp)
  554. long            *flagp;
  555. {
  556.     register char  *ret;
  557.     long             flags;
  558.  
  559.     *flagp = WORST;                /* Tentatively. */
  560.  
  561.     switch (*regparse++) {
  562.     case CARET:
  563.         ret = regnode(BOL);
  564.         break;
  565.     case DOLLAR:
  566.         ret = regnode(EOL);
  567.         break;
  568.     case DOT:
  569.         ret = regnode(ANY);
  570.         *flagp |= HASWIDTH | SIMPLE;
  571.         break;
  572.     case LSHBRAC:
  573.         ret = regnode(WORDSTART);
  574.         break;
  575.     case RSHBRAC:
  576.         ret = regnode(WORDEND);
  577.         break;
  578.     case LSQBRAC:{
  579.             register long    class;
  580.             register long    classend;
  581.  
  582.             if (*regparse == CARET) {        /* Complement of range. */
  583.                 ret = regnode(ANYBUT);
  584.                 regparse++;
  585.             } else
  586.                 ret = regnode(ANYOF);
  587.             if (*regparse == RSQBRAC || *regparse == '-')
  588.                 regc(*regparse++);
  589.             while (*regparse != '\0' && *regparse != RSQBRAC) {
  590.                 if (*regparse == '-') {
  591.                     regparse++;
  592.                     if (*regparse == RSQBRAC || *regparse == '\0')
  593.                         regc('-');
  594.                     else {
  595.                         class = (CHARBITS & *(regparse - 2)) + 1;
  596.                         classend = (CHARBITS & *(regparse));
  597.                         if (class > classend + 1)
  598.                             FAIL("invalid [] range");
  599.                         for (; class <= classend; class++)
  600.                             regc(class);
  601.                         regparse++;
  602.                     }
  603.                 } else
  604.                     regc(*regparse++);
  605.             }
  606.             regc('\0');
  607.             if (*regparse != RSQBRAC)
  608.                 FAIL("unmatched []");
  609.             regparse++;
  610.             *flagp |= HASWIDTH | SIMPLE;
  611.         }
  612.         break;
  613.     case LBRAC:
  614.         ret = reg(1, &flags);
  615.         if (ret == (char *)NULL)
  616.             return ((char *)NULL);
  617.         *flagp |= flags & (HASWIDTH | SPSTART);
  618.         break;
  619.     case '\0':
  620.     case OR_OP:
  621.     case RBRAC:
  622.         FAIL("internal urp");        /* Supposed to be caught earlier. */
  623.         break;
  624.     case ASTERIX:
  625.         FAIL("* follows nothing");
  626.         break;
  627.     default:{
  628.             register long    len;
  629.             register short  ender;
  630.  
  631.             regparse--;
  632.             for (len=0; regparse[len] &&
  633.                 !(regparse[len]&SPECIAL) && regparse[len] != RSQBRAC; len++) ;
  634.             if (len <= 0)
  635.                 {
  636.                 FAIL("internal disaster");
  637.                 }
  638.             ender = *(regparse + len);
  639.             if (len > 1 && ISMULT(ender))
  640.                 len--;                /* Back off clear of * operand. */
  641.             *flagp |= HASWIDTH;
  642.             if (len == 1)
  643.                 *flagp |= SIMPLE;
  644.             ret = regnode(EXACTLY);
  645.             while (len > 0) {
  646.                 regc(*regparse++);
  647.                 len--;
  648.             }
  649.             regc('\0');
  650.         }
  651.         break;
  652.     }
  653.  
  654.     return (ret);
  655. }
  656.  
  657. /*
  658.  - regnode - emit a node
  659.  */
  660. static char *regnode(op)
  661. char            op;
  662. {
  663.     register char  *ret;
  664.     register char  *ptr;
  665.  
  666.     ret = regcode;
  667.     if (ret == ®dummy) {
  668.         regsize += 3;
  669.         return (ret);
  670.     }
  671.     ptr = ret;
  672.     *ptr++ = op;
  673.     *ptr++ = '\0';                /* Null "nxt" pointer. */
  674.     *ptr++ = '\0';
  675.     regcode = ptr;
  676.  
  677.     return (ret);
  678. }
  679.  
  680. /*
  681.  - regc - emit (if appropriate) a byte of code
  682.  */
  683. static void regc(b)
  684. char            b;
  685. {
  686.     if (regcode != ®dummy)
  687.         *regcode++ = b;
  688.     else
  689.         regsize++;
  690. }
  691.  
  692. /*
  693.  - reginsert - insert an operator in front of already-emitted operand
  694.  *
  695.  * Means relocating the operand.
  696.  */
  697. static void reginsert(op, opnd)
  698. char            op;
  699. char           *opnd;
  700. {
  701.     register char  *src;
  702.     register char  *dst;
  703.     register char  *place;
  704.  
  705.     if (regcode == ®dummy) {
  706.         regsize += 3;
  707.         return;
  708.     }
  709.     src = regcode;
  710.     regcode += 3;
  711.     dst = regcode;
  712.     while (src > opnd)
  713.         *--dst = *--src;
  714.  
  715.     place = opnd;                /* Op node, where operand used to be. */
  716.     *place++ = op;
  717.     *place++ = '\0';
  718.     *place++ = '\0';
  719. }
  720.  
  721. /*
  722.  - regtail - set the next-pointer at the end of a node chain
  723.  */
  724. static void regtail(p, val)
  725. char           *p;
  726. char           *val;
  727. {
  728.     register char  *scan;
  729.     register char  *temp;
  730.     register long    offset;
  731.  
  732.     if (p == ®dummy)
  733.         return;
  734.  
  735.     /* Find last node. */
  736.     scan = p;
  737.     for (;;) {
  738.         temp = regnext(scan);
  739.         if (temp == (char *)NULL)
  740.             break;
  741.         scan = temp;
  742.     }
  743.  
  744.     if (OP(scan) == BACK)
  745.         offset = scan - val;
  746.     else
  747.         offset = val - scan;
  748.     *(scan + 1) = (offset >> 8) & 0377;
  749.     *(scan + 2) = offset & 0377;
  750. }
  751.  
  752. /*
  753.  - regoptail - regtail on operand of first argument; nop if operandless
  754.  */
  755. static void regoptail(p, val)
  756. char           *p;
  757. char           *val;
  758. {
  759.     /* "Operandless" and "op != BRANCH" are synonymous in practice. */
  760.     if (p == (char *)NULL || p == ®dummy || OP(p) != BRANCH)
  761.         return;
  762.     regtail(OPERAND(p), val);
  763. }
  764.  
  765. /*
  766.  * regexec and friends
  767.  */
  768.  
  769. /*
  770.  * Global work variables for regexec().
  771.  */
  772. static char    *reginput;        /* String-input pointer. */
  773. static char    *regbol;                /* Beginning of input, for ^ check. */
  774. static char   **regstartp;        /* Pointer to startp array. */
  775. static char   **regendp;        /* Ditto for endp. */
  776.  
  777. /*
  778.  * Forwards.
  779.  */
  780. static long      regtry();
  781. static long      regmatch();
  782. static long      regrepeat();
  783.  
  784. #ifdef DEBUG
  785. long             regnarrate = 0;
  786. void            regdump();
  787. static char    *regprop();
  788. #endif
  789.  
  790. /*
  791.  - regexec - match a regexp against a string
  792.  */
  793. pascal long regexec(register regexp *prog, register char  *string)
  794. {
  795.     register char  *s;
  796.  
  797.     /* Be paranoid... */
  798.     if (prog == (regexp *)NULL || string == (char *)NULL) {
  799.         regerror("NULL parameter");
  800.         return (0);
  801.     }
  802.     /* Check validity of program. */
  803.     if (UCHARAT(prog->program) != MAGIC) {
  804.         regerror("corrupted program");
  805.         return (0);
  806.     }
  807.     /* If there is a "must appear" string, look for it. */
  808.     if (prog->regmust != (char *)NULL) {
  809.         s = string;
  810.         while ((s = strcasechr(s, prog->regmust[0])) != (char *)NULL) {
  811.             if (strncasedifferent(s, prog->regmust, prog->regmlen) == 0)
  812.                 break;                /* Found it. */
  813.             s++;
  814.         }
  815.         if (s == (char *)NULL)                /* Not present. */
  816.             return (0);
  817.     }
  818.     /* Mark beginning of line for ^ . */
  819.     regbol = string;
  820.  
  821.     /* Simplest case:  anchored match need be tried only once. */
  822. /* PNL hack to handle \r, \n
  823.     if (prog->reganch)
  824.         return (regtry(prog, string));
  825. */
  826.  
  827.     /* Messy cases:  unanchored match. */
  828.     s = string;
  829.     if (prog->regstart != '\0')
  830.         /* We know what char it must start with. */
  831.         while ((s = strcasechr(s, prog->regstart)) != (char *)NULL) {
  832.             if (regtry(prog, s))
  833.                 return (1);
  834.             s++;
  835.         }
  836.     else
  837.         /* We don't -- general case. */
  838.         do {
  839.             if (regtry(prog, s))
  840.                 return (1);
  841.         } while (*s++ != '\0');
  842.  
  843.     /* Failure. */
  844.     return (0);
  845. }
  846.  
  847. /*
  848.  - regtry - try match at specific point
  849.  */
  850. static long regtry(regexp *prog, char *string)
  851. {
  852.     register long    i;
  853.     register char **sp;
  854.     register char **ep;
  855.  
  856.     reginput = string;
  857.     regstartp = prog->startp;
  858.     regendp = prog->endp;
  859.  
  860.     sp = prog->startp;
  861.     ep = prog->endp;
  862.     for (i = NSUBEXP; i > 0; i--) {
  863.         *sp++ = (char *)NULL;
  864.         *ep++ = (char *)NULL;
  865.     }
  866.     if (regmatch(prog->program + 1)) {
  867.         prog->startp[0] = string;
  868.         prog->endp[0] = reginput;
  869.         return (1);
  870.     } else
  871.         return (0);
  872. }
  873.  
  874. /*
  875.  - regmatch - main matching routine
  876.  *
  877.  * Conceptually the strategy is simple:  check to see whether the current
  878.  * node matches, call self recursively to see whether the rest matches,
  879.  * and then act accordingly.  In practice we make some effort to avoid
  880.  * recursion, in particular by going through "ordinary" nodes (that don't
  881.  * need to know whether the rest of the match failed) by a loop instead of
  882.  * by recursion.
  883.  */
  884. static long regmatch(char *prog)
  885. {
  886.     register char  *scan;        /* Current node. */
  887.     char           *nxt;        /* nxt node. */
  888.  
  889.     scan = prog;
  890. #ifdef DEBUG
  891.     if (scan != (char *)NULL && regnarrate)
  892.         fprintf(stderr, "%s(\n", regprop(scan));
  893. #endif
  894.     while (scan != (char *)NULL) {
  895. #ifdef DEBUG
  896.         if (regnarrate)
  897.             fprintf(stderr, "%s...\n", regprop(scan));
  898. #endif
  899.         nxt = regnext(scan);
  900.  
  901.         switch (OP(scan)) {
  902.         case BOL:
  903. /*
  904.             if (reginput != regbol)
  905.                 return (0);
  906. */
  907.             /* \r, \n hack PNL */
  908.             if (reginput != regbol && *(reginput-1) != '\r' && *(reginput-1) != '\n' )
  909.                 return (0);
  910.             break;
  911.         case EOL:
  912. /*
  913.             if (*reginput != '\0')
  914.                 return (0);
  915. */
  916.             /* \r, \n hack PNL */
  917.             if (*reginput != '\0' && *reginput != '\r' && *reginput != '\n')
  918.                 return (0);
  919.             break;
  920.         case ANY:
  921. /*
  922.             if (*reginput == '\0')
  923.                 return (0);
  924. */
  925.             /* \r, \n hack PNL */
  926.             if (*reginput == '\0' || *reginput == '\r' || *reginput == '\n')
  927.                 return (0);
  928.             reginput++;
  929.             break;
  930.         case WORDSTART:
  931.             if (reginput == regbol)
  932.                 break;
  933.             if (*reginput == '\0' ||
  934.                ISWORDPART( *(reginput-1) ) || !ISWORDPART( *reginput ) )
  935.                 return (0);
  936.             break;
  937.         case WORDEND:
  938.             if (*reginput == '\0')
  939.                 break;
  940.             if ( reginput == regbol ||
  941.                !ISWORDPART( *(reginput-1) ) || ISWORDPART( *reginput ) )
  942.                 return (0);
  943.             break;
  944.         case EXACTLY:{
  945.                 register long    len;
  946.                 register char  *opnd;
  947.  
  948.                 opnd = OPERAND(scan);
  949.                 /* Inline the first character, for speed. */
  950.                 /* toupper hack PNL */
  951.                 if (toupper(*opnd) != toupper(*reginput))
  952.                     return (0);
  953.                 len = strlen(opnd);
  954.                 /* toupper hack PNL */
  955.                 if (len > 1 && strncasedifferent(opnd, reginput, len) != 0)
  956.                     return (0);
  957.                 reginput += len;
  958.             }
  959.             break;
  960.         case ANYOF:
  961.             if (*reginput == '\0' || *reginput == '\r' || *reginput == '\n' || 
  962.                  strcasechr(OPERAND(scan), *reginput) == (char *)NULL)
  963.                 return (0);
  964.             reginput++;
  965.             break;
  966.         case ANYBUT:
  967.             if (*reginput == '\0' || *reginput == '\r' || *reginput == '\n' || 
  968.                  strcasechr(OPERAND(scan), *reginput) != (char *)NULL)
  969.                 return (0);
  970.             reginput++;
  971.             break;
  972.         case NOTHING:
  973.             break;
  974.         case BACK:
  975.             break;
  976.         case OPEN + 1:
  977.         case OPEN + 2:
  978.         case OPEN + 3:
  979.         case OPEN + 4:
  980.         case OPEN + 5:
  981.         case OPEN + 6:
  982.         case OPEN + 7:
  983.         case OPEN + 8:
  984.         case OPEN + 9:{
  985.                 register long    no;
  986.                 register char  *save;
  987.  
  988.                 no = OP(scan) - OPEN;
  989.                 save = reginput;
  990.  
  991.                 if (regmatch(nxt)) {
  992.                     /*
  993.                      * Don't set startp if some later invocation of the same
  994.                      * parentheses already has. 
  995.                      */
  996.                     if (regstartp[no] == (char *)NULL)
  997.                         regstartp[no] = save;
  998.                     return (1);
  999.                 } else
  1000.                     return (0);
  1001.             }
  1002.             break;
  1003.         case CLOSE + 1:
  1004.         case CLOSE + 2:
  1005.         case CLOSE + 3:
  1006.         case CLOSE + 4:
  1007.         case CLOSE + 5:
  1008.         case CLOSE + 6:
  1009.         case CLOSE + 7:
  1010.         case CLOSE + 8:
  1011.         case CLOSE + 9:{
  1012.                 register long    no;
  1013.                 register char  *save;
  1014.  
  1015.                 no = OP(scan) - CLOSE;
  1016.                 save = reginput;
  1017.  
  1018.                 if (regmatch(nxt)) {
  1019.                     /*
  1020.                      * Don't set endp if some later invocation of the same
  1021.                      * parentheses already has. 
  1022.                      */
  1023.                     if (regendp[no] == (char *)NULL)
  1024.                         regendp[no] = save;
  1025.                     return (1);
  1026.                 } else
  1027.                     return (0);
  1028.             }
  1029.             break;
  1030.         case BRANCH:{
  1031.                 register char  *save;
  1032.  
  1033.                 if (OP(nxt) != BRANCH)        /* No choice. */
  1034.                     nxt = OPERAND(scan);        /* Avoid recursion. */
  1035.                 else {
  1036.                     do {
  1037.                         save = reginput;
  1038.                         if (regmatch(OPERAND(scan)))
  1039.                             return (1);
  1040.                         reginput = save;
  1041.                         scan = regnext(scan);
  1042.                     } while (scan != (char *)NULL && OP(scan) == BRANCH);
  1043.                     return (0);
  1044.                     /* NOTREACHED */
  1045.                 }
  1046.             }
  1047.             break;
  1048.         case STAR:{
  1049.                 register char   nextch;
  1050.                 register long    no;
  1051.                 register char  *save;
  1052.                 register long    minimum;
  1053.  
  1054.                 /*
  1055.                  * Lookahead to avoid useless match attempts when we know
  1056.                  * what character comes next. 
  1057.                  */
  1058.                 nextch = '\0';
  1059.                 if (OP(nxt) == EXACTLY)
  1060.                     nextch = toupper(*OPERAND(nxt));
  1061.                 minimum = (OP(scan) == STAR) ? 0 : 1;
  1062.                 save = reginput;
  1063.                 no = regrepeat(OPERAND(scan));
  1064.                 while (no >= minimum) {
  1065.                     /* If it could work, try it. */
  1066.                     if (nextch == '\0' || toupper(*reginput) == nextch)
  1067.                         if (regmatch(nxt))
  1068.                             return (1);
  1069.                     /* Couldn't or didn't -- back up. */
  1070.                     no--;
  1071.                     reginput = save + no;
  1072.                 }
  1073.                 return (0);
  1074.             }
  1075.             break;
  1076.         case END:
  1077.             return (1);                /* Success! */
  1078.             break;
  1079.         default:
  1080.             regerror("memory corruption");
  1081.             return (0);
  1082.             break;
  1083.         }
  1084.  
  1085.         scan = nxt;
  1086.     }
  1087.  
  1088.     /*
  1089.      * We get here only if there's trouble -- normally "case END" is the
  1090.      * terminating point. 
  1091.      */
  1092.     regerror("corrupted pointers");
  1093.     return (0);
  1094. }
  1095.  
  1096. /*
  1097.  - regrepeat - repeatedly match something simple, report how many
  1098.  */
  1099. static long regrepeat(char *p)
  1100. {
  1101.     register long    count = 0;
  1102.     register char  *scan;
  1103.     register char  *opnd;
  1104.  
  1105.     scan = reginput;
  1106.     opnd = OPERAND(p);
  1107.     switch (OP(p)) {
  1108.     case ANY:
  1109.  
  1110. /*
  1111.         count = strlen(scan);
  1112.         scan += count;
  1113. */
  1114.         /* . doesn't match \r, \n hack PNL */
  1115.         while (*scan && (*scan != '\r') && (*scan != '\n')) {
  1116.             count++;
  1117.             scan++;
  1118.         }
  1119.         break;
  1120.     case EXACTLY:
  1121.         while (toupper(*opnd) == toupper(*scan)) {
  1122.             count++;
  1123.             scan++;
  1124.         }
  1125.         break;
  1126.     case ANYOF:
  1127.         while (*scan != '\0' && *scan != '\r' && *scan != '\n' && strcasechr(opnd, *scan) != (char *)NULL) {
  1128.             count++;
  1129.             scan++;
  1130.         }
  1131.         break;
  1132.     case ANYBUT:
  1133.         while (*scan != '\0' && *scan != '\r' && *scan != '\n' && strcasechr(opnd, *scan) == (char *)NULL) {
  1134.             count++;
  1135.             scan++;
  1136.         }
  1137.         break;
  1138.     default:                        /* Oh dear.  Called inappropriately. */
  1139.         regerror("internal foulup");
  1140.         count = 0;                /* Best compromise. */
  1141.         break;
  1142.     }
  1143.     reginput = scan;
  1144.  
  1145.     return (count);
  1146. }
  1147.  
  1148.  
  1149. /*
  1150.  - regnext - dig the "nxt" pointer out of a node
  1151.  */
  1152. static char *regnext(register char *p)
  1153. {
  1154.     register long    offset;
  1155.  
  1156.     if (p == ®dummy)
  1157.         return ((char *)NULL);
  1158.  
  1159.     offset = NEXT(p);
  1160.     if (offset == 0)
  1161.         return ((char *)NULL);
  1162.  
  1163.     if (OP(p) == BACK)
  1164.         return (p - offset);
  1165.     else
  1166.         return (p + offset);
  1167. }
  1168.  
  1169. #ifdef DEBUG
  1170.  
  1171. static char    *regprop();
  1172.  
  1173. /*
  1174.  - regdump - dump a regexp onto stdout in vaguely comprehensible form
  1175.  */
  1176. void regdump(regexp *r)
  1177. {
  1178.     register char  *s;
  1179.     register char   op = EXACTLY;        /* Arbitrary non-END op. */
  1180.     register char  *nxt;
  1181.  
  1182.     s = r->program + 1;
  1183.     while (op != END) {                /* While that wasn't END last time... */
  1184.         op = OP(s);
  1185.         printf("%2d%s", (long)(s - r->program), regprop(s));        /* Where, what. */
  1186.         nxt = regnext(s);
  1187.         if (nxt == (char *)NULL)        /* nxt ptr. */
  1188.             printf("(0)");
  1189.         else
  1190.             printf("(%d)", (long)((s - r->program) + (nxt - s)));
  1191.         s += 3;
  1192.         if (op == ANYOF || op == ANYBUT || op == EXACTLY) {
  1193.             /* Literal string, where present. */
  1194.             while (*s != '\0') {
  1195.                 putchar(*s);
  1196.                 s++;
  1197.             }
  1198.             s++;
  1199.         }
  1200.         putchar('\n');
  1201.     }
  1202.  
  1203.     /* Header fields of interest. */
  1204.     if (r->regstart != '\0')
  1205.         printf("start `%c' ", r->regstart);
  1206.     if (r->reganch)
  1207.         printf("anchored ");
  1208.     if (r->regmust != (char *)NULL)
  1209.         printf("must have \"%s\"", r->regmust);
  1210.     printf("\n");
  1211. }
  1212.  
  1213. /*
  1214.  - regprop - printable representation of opcode
  1215.  */
  1216. static char *regprop(char *op)
  1217. {
  1218.     register char  *p;
  1219.     static char     buf[50];
  1220.  
  1221.     strcpy(buf, ":");
  1222.  
  1223.     switch (OP(op)) {
  1224.     case BOL:
  1225.         p = "BOL";
  1226.         break;
  1227.     case EOL:
  1228.         p = "EOL";
  1229.         break;
  1230.     case ANY:
  1231.         p = "ANY";
  1232.         break;
  1233.     case ANYOF:
  1234.         p = "ANYOF";
  1235.         break;
  1236.     case ANYBUT:
  1237.         p = "ANYBUT";
  1238.         break;
  1239.     case BRANCH:
  1240.         p = "BRANCH";
  1241.         break;
  1242.     case EXACTLY:
  1243.         p = "EXACTLY";
  1244.         break;
  1245.     case NOTHING:
  1246.         p = "NOTHING";
  1247.         break;
  1248.     case BACK:
  1249.         p = "BACK";
  1250.         break;
  1251.     case END:
  1252.         p = "END";
  1253.         break;
  1254.     case OPEN + 1:
  1255.     case OPEN + 2:
  1256.     case OPEN + 3:
  1257.     case OPEN + 4:
  1258.     case OPEN + 5:
  1259.     case OPEN + 6:
  1260.     case OPEN + 7:
  1261.     case OPEN + 8:
  1262.     case OPEN + 9:
  1263.         sprintf(buf + strlen(buf), "OPEN%d", OP(op) - OPEN);
  1264.         p = (char *)NULL;
  1265.         break;
  1266.     case CLOSE + 1:
  1267.     case CLOSE + 2:
  1268.     case CLOSE + 3:
  1269.     case CLOSE + 4:
  1270.     case CLOSE + 5:
  1271.     case CLOSE + 6:
  1272.     case CLOSE + 7:
  1273.     case CLOSE + 8:
  1274.     case CLOSE + 9:
  1275.         sprintf(buf + strlen(buf), "CLOSE%d", OP(op) - CLOSE);
  1276.         p = (char *)NULL;
  1277.         break;
  1278.     case STAR:
  1279.         p = "STAR";
  1280.         break;
  1281.     default:
  1282.         regerror("corrupted opcode");
  1283.         break;
  1284.     }
  1285.     if (p != (char *)NULL)
  1286.         strcat(buf, p);
  1287.     return (buf);
  1288. }
  1289. #endif
  1290.  
  1291. /*
  1292.  - regsub - perform substitutions after a regexp match
  1293.  */
  1294. pascal char *regsub(regexp *prog, char *source, char *dest, long n)
  1295. {
  1296.     register char  *src;
  1297.     register char  *dst;
  1298.     register char   c;
  1299.     register long    no;
  1300.     register long    len;
  1301.     extern char    *strncpy();
  1302.  
  1303.     if (prog == (regexp *)NULL || 
  1304.         source == (char *)NULL || dest == (char *)NULL) {
  1305.         regerror("NULL parm to regsub");
  1306.         return NULL;
  1307.     }
  1308.     if (UCHARAT(prog->program) != MAGIC) {
  1309.         regerror("damaged regexp fed to regsub");
  1310.         return NULL;
  1311.     }
  1312.     src = source;
  1313.     dst = dest;
  1314.     while ((c = *src++) != '\0') {
  1315.         if (c == '&')
  1316.             no = 0;
  1317.         else if (c == '\\' && '0' <= *src && *src <= '9')
  1318.             no = *src++ - '0';
  1319.         else
  1320.             no = -1;
  1321.  
  1322.         if (no < 0) {                /* Ordinary character. */
  1323.             if (c == '\\' && (*src == '\\' || *src == '&'))
  1324.                 c = *src++;
  1325.             if (--n < 0) {                                /* amylaar */
  1326.                 regerror("line too long");
  1327.                 return NULL;
  1328.             }
  1329.             *dst++ = c;
  1330.         } else if (prog->startp[no] != (char *)NULL && 
  1331.                    prog->endp[no] != (char *)NULL) {
  1332.             len = prog->endp[no] - prog->startp[no];
  1333.             if ( (n-=len) < 0 ) {                /* amylaar */
  1334.                 regerror("line too long");
  1335.                 return NULL;
  1336.             }
  1337.             strncpy(dst, prog->startp[no], len);
  1338.             dst += len;
  1339.             if (len != 0 && *(dst - 1) == '\0') {        /* strncpy hit NUL. */
  1340.                 regerror("damaged match string");
  1341.                 return NULL;
  1342.             }
  1343.         }
  1344.     }
  1345.     if (--n < 0) {                        /* amylaar */
  1346.             regerror("line too long");
  1347.             return NULL;
  1348.     }
  1349.     *dst = '\0';
  1350.     return dst;
  1351. }
  1352.  
  1353.  
  1354.